Indoor localization has gained considerable attention over the last decade due to the enormous potential in the technology and the significant challenges facing this area of research [1].
Localization in traditional line of sight (LOS) environments such as outdoors has been a success as exemplified by the popular Global Positioning System (GPS). Extending GPS's success to indoor environments, however, faces considerable fundamental challenges. The most notable of those are the non-LOS (NLOS) environment and severe multipath propagation phenomena [1, 2].
Typically there are two main philosophies to localize nodes/mobile terminals in an indoor environment.
The first is localization based on extracting the ranging metrics from existing/deployed infrastructure (Time of Arrival (TOA), Received Signal Strength (RSS), Angle of Arrival (AOA) or any combination of them) and performing well known tri-lateration techniques. This technique is highly affected by the system bandwidth and the propagation environment (NLOS) and it is usually performed in real-time without any prior set up or training.
The second approach is based on location fingerprinting. The basic idea of location fingerprinting is to create a database of “fingerprints” constructed from measured channel parameters that are extracted from available wireless network infrastructures such as access points (APs) in an offline phase across a given indoor environment. This fingerprinting database is typically formed by creating a grid of points (e.g. in 1 m squares) across an area or floor of an indoor environment and in each grid location a fingerprint is constructed from measurements received from all available APs. Location estimates are then obtained in the online phase by comparing the measured fingerprint parameters to the fingerprinting database by using pattern matching algorithms. The signature/fingerprint closest to the measured one corresponds to the estimated location.
FIG. 1 illustrates the difference between the two localization approaches in schematic form. FIG. 1a shows ranging and tri-lateration based on RSS, TOA, AOA or any combination of those techniques. FIG. 1b shows fingerprinting (e.g. using RSS or CIR). The red dots are measured locations in offline stage. Measurements in online stage are compared using pattern matching algorithms to the database and the center of grid with closest match is taken as the estimated position.
Existing location fingerprinting techniques are typically categorized based on the type of collected signal parameter(s). The 3 major channel/signal parameters that have been used for the fingerprints are: Received Signal Strength (RSS); time-domain Channel Impulse Response (CIR); frequency-domain Channel Transfer Function (CTF) and Frequency Channel Coherence Function (FCF). One of the earliest and simplest fingerprinting techniques is RSS-based fingerprinting. The simplicity stems from the fact that RSS measurement values are readily available in IEEE 802.11 standards implementation [3]. As a result a fingerprint vector can be easily constructed from RSS measurements received from the available APs.
A more robust fingerprinting mechanism is based on the CIR. Typically, the CIR provides a more unique but complex metric that can be used as a fingerprint, since it is a representation of the multipath channel in the time-domain [4, 5]. The uniqueness stems from the fact that the amplitude and delay of the multipath arrivals at each location are different because of the complex interaction of the RF signal and the indoor environment (reflections and diffractions of signals from walls, objects, etc.). Thus CIR-based fingerprinting techniques thrive on the multipath environment where the channel impulse response at each location is a unique signature. Since the multipath structure is unique and varies from one location to the next, it is possible to identify a location by a single AP. The CIR-fingerprinting technique that relies on the multipath structure to uniquely identify a given location was first introduced by US Wireless Corp. of San Ramon, Calif. [7].
Fingerprinting using the channel impulse response (multipath structure) was also proposed for cellular UMTS localization [8, 9]. The CIR-based fingerprinting algorithm was also successfully implemented in a neural network pattern recognition system which achieved good localization accuracy inside a mine [4, 5].
CIR-based fingerprinting can be further improved by implementing an antenna array approach where the spatial characteristics of the channel are captured resulting in a new metric defined by Power Spatial Delay Profile (PSDP). The CIR contains the magnitude of the delay components which removes all the phase information and as a result this technique cannot exploit the additional spatial information [10].
An improvement to CIR-based fingerprinting has been proposed [11] where a non-parametric regression technique (Nadaraya Watson Kernel estimator) is used as the location estimator. In addition the authors of the above document introduce regional smoothing and logarithmic scale transformation to further improve performance.
CIR fingerprinting-based localization has been further investigated for UWB signals in [12] where the effect of system bandwidth on the probability of false alarm and robustness of estimation is investigated through channel measurements in an indoor environment. In general increasing the system bandwidth improves accuracy and reliability significantly [12].
Analogous to the time domain impulse response, the CTF can also be used for fingerprinting. The CTF contains the multipath channel information in the form of complex samples in the frequency domain. The authors in [12] have further proposed the CTF correlation fingerprint which is more stable and has superior performance. A patent application proposes a similar technique that integrates FCF-based (autocorrelation of CTF) fingerprinting in existing OFDM-based systems (such as WLANs) [6].
An RSS-based fingerprint is a vector of dimension M, where M is the number of available APs. The CIR-, CTF- or FCF-based fingerprints are matrices with dimension M by N, where N is the number of samples in the CIR, CTF or FCF vector. The disadvantage of RSS-based fingerprinting is that the fingerprint structure lacks uniqueness and precision in distinguishing between two locations. Thus RSS fingerprints can be very similar in two different locations due to the signal power fluctuations. CIR, CTF and FCF provide robust fingerprints but the techniques require storage of matrices and pattern recognition between matrices. For example, when comparing two fingerprints, samples of the CIR, CTF or FCF matrices have to be compared against each other which can be computationally intensive for medium to large size databases (typical indoor environments). Similarly, the storage requirements can be prohibitive.
The RSS-based localization technique, although simple, suffers from low precision due to the significant fluctuation of power due to multipath and shadowing. The more robust CIR, CTF or FCF based fingerprinting techniques exhibit higher accuracy but suffer from computational and storage burdens due to the manipulation and storage of large matrices (especially for medium-large indoor areas).
FIG. 2 provides an overview of known methods of constructing a fingerprint in a given location. In step (a) a mobile terminal at location X conducts measurements to 3 APs and captures RF signals. In step (b) channel metrics are extracted from the 3 RF signals and a fingerprint is created. For RSS-based fingerprinting in this example, the fingerprint will be a vector of 3 RSS values, while for CIR- and FCF-based fingerprinting in this example the fingerprint will be a matrix with dimension 3 by N, where N is the number of samples in the CIR or the FCF vector.
In addition to the type of collected signal parameters, existing location fingerprinting techniques vary according to the pattern recognition/position estimation approach used. The most popular are probabilistic methods, k-nearest neighbor (kNN), neural networks, support vector machine (SVM) and smallest M-vertex polygon (SMP) [13].
An overview of these different pattern recognition techniques will be given. Although most of them are RSS-based techniques, the extension to CIR- or FCF-based techniques can be easily implemented.
One of the earliest RSS-based fingerprinting methods is the RADAR system [3]. The basic idea behind the RADAR system is to create an offline database composed of RSS measurements from overlapping coverage of APs. In the online phase the system employs the nearest neighbor algorithm where the measured RSS vector is compared to the database of stored RSS vectors and the position related to the shortest Euclidean distance is chosen as the estimated position.
The nearest neighbor technique can be also extended to the kNN where the algorithm returns the location estimate as the average of the coordinates of the k training locations whose fingerprint vectors have shortest Euclidean distances to the online RSS vectors. A similar RSS-based fingerprinting technique that weighs the k nearest neighbors by the reciprocal of their signal space Euclidean distance to the RSS vectors in the database has been proposed in [14]. RSS-based fingerprinting techniques that are based on a probabilistic approach have been reported in [15, 16, 17, 18], where the conditional expectation is used as the estimator which minimizes the conditional mean square error. The training data are used to construct the probability density function (PDF) for the location and the fingerprint vectors. Mathematical expressions of the location estimate are close to the Nadaraya-Watson Kernel Regression estimator but the elements of the fingerprint vector are assumed to be statistically independent from each other (simplicity of computation but not always true in practice).
In [19], the authors propose a joint clustering RSS-based technique for indoor localization based on a probabilistic method.
In [20], the authors introduce the LOCATOR algorithm which is an RSS-based fingerprinting technique but incorporates different approaches. Specifically, in the radio map building phase, the radio map is subdivided into clusters to reduce the computation cost in the location estimation phase. The authors further use RSS distribution functions, clustering and interpolations to improve the performance.
In [21] the Horus RSS-based fingerprinting technique models the RSS distribution received from APs using parametric and non-parametric distributions and exploits this information to reduce temporal variations.
Neural network pattern recognition techniques for RSS-based location fingerprinting have been reported in [22, 23]. RSS-based fingerprinting techniques based on support vector machines have been reported in [24, 25].
Recently the authors in [26] demonstrated further improvements to RSS-based fingerprinting by using an averaging technique in the logarithmic spectrum domain to mitigate the noise resulting from the multipath.
Performance evaluation of different RSS-based fingerprinting techniques is presented in [27]. Specifically, the authors compare the performance of probabilistic method, kNN and neural networks as the three most popular machine techniques. The results of analysis and experiments reveal that kNN reports the best overall performance for indoor positioning. The performance of histogram, nearest neighbor, parametric and kernel location fingerprinting techniques were evaluated in [28, 29]. The results revealed that the performance of the nearest neighbor technique fared the same or better than the other techniques depending on the scenario.
In typical fingerprinting-based location systems a fingerprint database is created in an offline stage by constructing the fingerprints/signatures (through measurement of channel parameters such as RSS or CIR/CTF) in different locations across a grid. In the online phase a mobile terminal in an unknown location constructs a fingerprint by measuring channel parameters such as RSS or CIR to all APs within its coverage. This measured fingerprint is then compared to the offline database and the position is estimated using pattern recognition techniques. The simplest pattern recognition technique is the closest neighbor where the position is estimated by selecting the location of the fingerprint in the database that is the closest (smallest distance in vector space) to the online measured fingerprint.
The fingerprint database is typically created by gridding a floor of a room/office in a given indoor environment. The grid is composed of N locations that are spaced by Δ. Note that a smaller Δ means denser grid that increases the cost of the site survey and increases the amount of data stored. For some channel parameters it might seem that the denser the grid the better the performance. For RSS-based fingerprinting techniques, it has been shown that increasing the density of the grid beyond a certain point can improve the accuracy but not the precision or probability of correctly matching the fingerprint because two points on the grid are too close to one another and maybe very similar [44].
The coordinates of a location on the grid are pj=[xj, yj]T where xj and yj are the x- and y-coordinates of the jth location and jε[1, N]. The fingerprint/signature at each grid location is given by the vector Zj=[z1j, . . . , zMj]T and each element is a measured parameter of the channel (e.g. RSS) from one of the mth APs where mε[1, M] and M is the total number of APs. In realistic situations it is common that in a given grid location some APs will be too far to be detected and as a result a zero can be inserted for the element where the mth AP cannot be detected, i.e. the jth grid point pj is out of the mth AP's coverage. In the pattern recognition stage, an estimate of the position {circumflex over (p)}=[{circumflex over (x)}, ŷ]T can be determined by the choosing the closest neighbor or the offline fingerprint, Zj, with the minimum Euclidean distance to the online fingerprint v=[v1, . . . , vM]T which is given by
                              d          min                =                                            arg              ⁢                                                          ⁢              min                                      p              j                                ⁢                      {                                                                          Z                  j                                -                v                                                    }                                              (        1        )            where the position that minimizes (1) is the estimate, that is {circumflex over (p)}=pj. Zj and v are M×1 vectors in the case the elements are scalar RSS measurements and M×Ns matrices when the fingerprints are constructed from CIRs or CTFs/FCFs vectors where Ns is the number of samples. Note that using CIR or CTFs as fingerprints increases the memory storage and processing requirements. In practice, Z is usually a vector (or matrix) of averaged channel parameters while v is a vector (or matrix) of instantaneous channel measurements. The performance of pattern recognition can be improved when both the online and offline fingerprints are average of the channel parameters, but this is not always feasible in practice.
An improvement to (1) is the kNN technique [4] which estimates the position as a weighted sum of the positions corresponding to the k minimum distance fingerprints on the grid. The kNN can be iteratively determined by [30]:
                              N          k                =                                            arg              ⁢                                                          ⁢              min                                      p                              j                ∈                N                                              ⁢                      {                                                            [                                                                                                        Z                        j                                            -                      v                                                                            ]                                ⁢                \                ⁢                                  p                  j                                            ∉                              N                                  k                  -                  1                                                      }                                              (        2        )            
The estimated position is then given by (3)
                              p          ^                =                                            ∑                              i                =                1                            k                        ⁢                                          (                                  1                  /                                      d                    i                                                  )                            ⁢                              p                i                                                                        ∑                              i                =                1                            k                        ⁢                          (                              1                /                                  d                  i                                            )                                                          (        3        )            where di=∥Zi−v∥ is the Euclidean distance between the ith position in the grid and the online fingerprint.
More complicated pattern recognition algorithms have been proposed such as the probabilistic (conditional mean)/Bayesian [15-18], parametric and non-parametric distribution [11, 21], neural network [4, 22, 23] and support vector machines [24, 25].
A performance evaluation of different pattern recognition techniques for RSS-based fingerprinting has been reported in [27] which compared kNN, probabilistic method and neural networks. The results of simulations revealed that the kNN reported the best overall performance for indoor fingerprint localization. In addition [28, 29] evaluated the performance of nearest neighbor, parametric and kernel location fingerprinting techniques and the results showed that nearest neighbor performs as well or better than the other techniques depending on the scenario.